package leetcode.code1329;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {

	int m, n;

	public int[][] diagonalSort(int[][] mat) {
		m = mat.length;
		n = mat[0].length;
		for (int j = 0; j < n; j++) {
			this.f(mat, 0, j, new ArrayList<>());
		}
		for (int i = 1; i < m; i++) {
			this.f(mat, i, 0, new ArrayList<>());
		}
		return mat;
	}

	private void f(int[][] mat, int x, int y, List<Integer> list) {
		if (x == m || y == n) {
			Collections.sort(list);
			this.s(mat, x - 1, y - 1, list, list.size() - 1);
			return;
		}
		list.add(mat[x][y]);
		this.f(mat, x + 1, y + 1, list);
	}

	private void s(int[][] mat, int i, int j, List<Integer> list, int k) {
		if (k < 0) {
			return;
		}
		mat[i][j] = list.get(k);
		this.s(mat, i - 1, j - 1, list, k - 1);
	}

}
